package com.lxm.leetcode;

import java.util.*;

/**
 * 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 * <p>
 * 两棵树重复是指它们具有相同的结构以及相同的结点值。
 * <p>
 * 示例 1：
 * <p>
 * 1
 * / \
 * 2   3
 * /   / \
 * 4   2   4
 * /
 * 4
 * 下面是两个重复的子树：
 * <p>
 * 2
 * /
 * 4
 * 和
 * <p>
 * 4
 * 因此，你需要以列表的形式返回上述重复子树的根结点
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-duplicate-subtrees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Question652 {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<TreeNode> list = new ArrayList<>();
        Map<String, Boolean> cachedMap = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode t = queue.poll();
            String str = traverse(t);
            Boolean flag = null;
            if ((flag = cachedMap.get(str)) != null && !flag) {
                list.add(t);
                cachedMap.put(str, Boolean.TRUE);
            } else if (flag == null) {
                cachedMap.put(str, Boolean.FALSE);
            }
            if (t.left != null) {
                queue.offer(t.left);
            }
            if (t.right != null) {
                queue.offer(t.right);
            }
        }
        return list;
    }

    private String traverse(TreeNode n) {
        if (n == null) {
            return "";
        }
        String left = traverse(n.left);
        String right = traverse(n.right);
        return left + "#" + right + "#" + n.val;
    }

    public static void main(String[] args){
        TreeNode l3_1 = new TreeNode(1, null, null);
        TreeNode l3_2 = new TreeNode(12, null, null);
        TreeNode l3_3 = new TreeNode(1, null, null);
        TreeNode l3_4 = new TreeNode(1, null, null);

        TreeNode l2_1 = new TreeNode(2, l3_1, l3_2);
        TreeNode l2_2 = new TreeNode(22, l3_3, l3_4);

        TreeNode l1_1 = new TreeNode(10, l2_1, l2_2);

        Question652 test = new Question652();
        List<TreeNode> result = test.findDuplicateSubtrees(l1_1);
        System.out.println(result);
    }
}
